#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution
{
public:
    int countTexts(string pressedKeys)
    {
        vector<long> dp3 = {1, 1, 2, 4};
        vector<long> dp4 = {1, 1, 2, 4, 8};
        char last = pressedKeys[0];
        int count = 0;
        long result = 1;
        long mod = 1000'000'007;
        auto get4 = [&](int n)
        {
            for (int i = dp4.size(); i <= n; i++)
            {
                dp4.push_back((dp4[i - 1] + dp4[i - 2] + dp4[i - 3] + dp4[i - 4]) % mod);
            }
            return dp4[n];
        };

        auto get3 = [&](int n)
        {
            for (int i = dp3.size(); i <= n; i++)
            {
                dp3.push_back((dp3[i - 1] + dp3[i - 2] + dp3[i - 3]) % mod);
            }
            return dp3[n];
        };

        for (auto c : pressedKeys)
        {
            if (c == last)
                count++;
            else
            {
                if (last == '7' || last == '9')
                {
                    result *= get4(count);
                    result %= mod;
                }
                else
                {
                    result *= get3(count);
                    result %= mod;
                }
                last = c;
                count = 1;
            }
        }
        if (last == '7' || last == '9')
        {
            result *= get4(count);
            result %= mod;
        }
        else
        {
            result *= get3(count);
            result %= mod;
        }
        return result;
    }
};
int main()
{
    cout << "Code2226" << endl;
    Solution s;
    cout << s.countTexts("222222222222222222222222222222222222") << endl;
    return 0;
}